Section: Software

Scotch

Participant : François Pellegrini [corresponding member] .

Scotch (http://www.labri.fr/~pelegrin/scotch/ ) is a software package for parallel and sequential sparse matrix ordering, parallel and sequential graph partitioning, as well as sequential static mapping, and mesh and hypergraph partitioning.

The initial purpose of Scotch was to compute high-quality partitions and static mappings of valuated graphs representing parallel computations and target architectures of arbitrary topologies. The original contribution consisted in developing a “divide and conquer” algorithm in which processes are recursively mapped onto processors by using graph bisection algorithms that are applied both to the process graph and to the architecture graph. This allows the mapper to take into account the topology and heterogeneity of the valuated graph which models the interconnection network and its resources (processor speed, link bandwidth). As new multicore, multinode parallel machines tend to be less uniform in terms of memory latency and communication bandwidth, this feature is regaining interest.

The software has then been extended in order to produce vertex separators instead of edge separators, using a multilevel framework. Recursive vertex separation is used to compute orderings of the unknowns of large sparse linear systems, which both preserve sparsity when factorizing the matrix and exhibit concurrency for computing and solving the factored matrix in parallel.

Version 5.0 of Scotch , released on August 2007, was the first version to comprise parallel routines. This extension, called PT-Scotch (for “Parallel Threaded Scotch ”), is based on a distributed memory model, and makes use of the MPI and, optionally, Posix thread APIs. A distributed graph structure has been defined, which allows users to reserve vertex indices on each processor for future local adaptive refinement. Its parallel graph ordering routine provides orderings which are of the same quality as the ones yielded by the sequential Scotch ordering routine, while competing software ParMETIS experiences a severe loss of quality when the number of processors increase. Scotch 5.0 was released under the CeCILL-C free/libre software license, and has been registered at APP (“Agence pour la Protection des Programmes”).

Version 5.1 of Scotch , released on September 2008, extended the parallel features of PT-Scotch , which can now compute graph partitions in parallel by means of a parallel recursive bipartitioning framework. Release 5.1.10 had made Scotch the first full 64-bit implementation of a general purpose graph partitioner, so that PT-Scotch has been able to successfully break the “32-bit” barrier and partition a graph above 2 billion vertices, spread across 2048 processors, at the French CCRT computer center.

Version 6.0 , about to be released, offers new sequential features: static mapping with fixed vertices, static remapping, and static remapping with fixed vertices.

Scotch has been integrated in numerous third-party software, which indirectly contribute to its diffusion. For instance, it is used by the Zoltan module of the Trilinos software (SANDIA Labs), by Code_Aster Libre , a GPLed thermal and mechanical analysis software developed by French state-owned electricity producer EDF, by the parallel solvers MUMPS (ENSEEITH/IRIT, LIP and LaBRI), SuperLUDist (U.C. Berkeley), PaStiX (LaBRI) and HIPS (LaBRI), as well as by several other scientific computing software.